package com.xixi.dataStructure.queue;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <p>English description is not available for the problem. Please switch to Chinese.</p>
 *
 * <div><div>Related Topics</div><div><li>队列</li><li>滑动窗口</li><li>单调队列</li><li>堆（优先队列）</li></div></div><br><div><li>👍 508</li><li>👎 0</li></div>
 */

//leetcode submit region begin(Prohibit modification and deletion)
class ID_Offer_59_I_HuaDongChuangKouDeZuiDaZhiLCOF {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        if (len == 1) return nums;

        Deque<Integer> maxNow = new ArrayDeque<>(k);

        int i = 0;
        while (i < k) {

            while (!maxNow.isEmpty() && maxNow.peekLast() < nums[i]) { //相等的poll出去可能会造成队列为空。比如窗口【543212345】，此时队列应为【5，5】
                maxNow.pollLast(); //前面比nums[i]小的对max都没影响
            }
            maxNow.offer(nums[i]);
            i++;
        }

        //i==k now


        int[] res = new int[len - k + 1];
        res[0] = maxNow.peekFirst();
        while (i < len) {
            //当前处理 i = k
            //滑动窗口
            if (nums[i - k] == maxNow.peekFirst()) { //滑出
                maxNow.pollFirst(); //该弹出了
            }
            //划入
            while (!maxNow.isEmpty() && maxNow.peekLast() < nums[i]) { //相等的poll出去可能会造成队列为空。比如窗口【543212345】，此时队列应为【5，5】
                maxNow.pollLast(); //前面比nums[i]小的对max都没影响
            }
            maxNow.offer(nums[i]);
            res[i - k + 1] = maxNow.peekFirst(); //记录
            i++;
        }

        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
